﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.Utils;

namespace Algoritmia.DataStructures.Lists
{
    public class LinkedList<T> : IList<T>
    {
        private class Node
        {
            public T Data;
            public Node Prev, Next;
            public Node(T data, Node prev=null, Node next=null)
            {
                Data = data;
                Prev = prev;
                Next = next;
            }
        }

        private Node _first, _last;
        private int _count;
        private readonly EqualityComparison<T> _equalityComparison;

        public LinkedList( IEnumerable<T> items=null, EqualityComparison<T> equalityComparison = null )
        {
            items = items ?? Enumerable.Empty<T>();
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
            foreach (var item in items)
            {
                Add(item);
            }
        }

        #region IList<T> Members

        public void Add(T elem)
        {
            if (_count == 0)
            {
                _first = _last = new Node(elem);
            }
            else 
            {
                var aux = new Node(elem, _last);
                _last.Next = aux;
                _last = aux;
            }
            _count++;
        }

        public void Clear()
        {
            _first = _last = null;
            _count = 0;
        }

        public bool Contains(T item)
        {
            Node aux = _first;
            while (aux != null)
            {
                if (_equalityComparison(item, aux.Data))
                    return true;
                aux = aux.Next;
            }
            return false;
        }

        private Node GetNodeAt(int index)
        {
            Node aux;
            int counter;
            if (index > _count / 2)
            {
                counter = _count-1;
                aux = _last;
                while (counter > index && aux != null)
                {
                    aux = aux.Prev;
                    counter--;
                }
                return aux;
            }
            counter = 0;
            aux = _first;
            while (counter < index && aux != null)
            {
                aux = aux.Next; counter++;
            }
            return aux;
        }

        public T this[int index]
        {
            get
            {
                if (index < 0 || index >= _count)
                {
                    throw new IndexOutOfRangeException();
                }
                return GetNodeAt(index).Data;

            }
            set
            {
                if (index < 0 || index >= _count)
                {
                    throw new IndexOutOfRangeException();
                }
                GetNodeAt(index).Data = value;
            }
        }

        public int IndexOf(T elem)
        {
            Node aux = _first;
            int i = 0;
            while (aux != null)
            {
                if (_equalityComparison(elem, aux.Data))
                    return i;
                aux = aux.Next;
                i++;
            }
            return -1;
        }

        public void InsertAt(T elem, int index)
        {
            if (index < 0 || index > _count)
            {
                throw new ArgumentOutOfRangeException();
            }

            if (index == _count)
            {
                Add(elem);
            }
            else
            {
                var next = GetNodeAt(index);
                var previous = next != null ? next.Prev : null;
                var newNode = new Node(elem, previous, next);

                //if next == null , index == count.
                //In this execution flow next never will be null.
                next.Prev = newNode;
                if (previous != null)
                    previous.Next = newNode;
                else
                    _first = newNode;
                _count++;
            }
        }

        public bool Remove(T item)
        {
            Node aux = _first;
            while (aux != null)
            {
                if (_equalityComparison(item, aux.Data))
                {
                    if (aux.Prev != null)
                        aux.Prev.Next = aux.Next;
                    else
                        _first = aux.Next;
                    if (aux.Next != null)
                        aux.Next.Prev = aux.Prev;
                    else
                        _last = aux.Prev;
                    _count--;
                    return true;
                }
                aux = aux.Next;
            }
            return false;
        }

        public void RemoveAt(int index)
        {
            if (index < 0 || index >= _count)
            {
                throw new ArgumentOutOfRangeException();
            }

            Node node = GetNodeAt(index);
            if (node.Prev != null)
                node.Prev.Next = node.Next;
            else
                _first = node.Next;
            if (node.Next != null)
                node.Next.Prev = node.Prev;
            else
                _last = node.Prev;
            _count--;
           
        }

        #endregion

        #region ICountable Members

        public int Count
        {
            get { return _count; }
        }

        #endregion

        #region IEnumerable<T> Members

        public IEnumerator<T> GetEnumerator()
        {
            Node aux = _first;
            while (aux != null)
            {
                yield return aux.Data;
                aux = aux.Next;
            }
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        public override string ToString()
        {
            return String.Format("{0} <{1}> [{2}]", GetType().Name, typeof(T).Name, string.Join(", ", this));
        }
    }
}
